package branch_and_price;

import ilog.concert.IloException;

import java.util.ArrayList;

/**
 * 列生成算法
 * 里面使用标号法找到检验数为负的列，再把负列添加进去
 * 在定价问题上，使用的是标号法生成新的路径
 */
public class CG {
    private Data data;
    private double tolerance = 0.0001; // 用于计算的某数字，无特殊意义
    private int dp_col_size; // 同时添加的负检验数列的最大数量
    private long oneI;
    private long oneII;

    // forward non-extend labels for each points【未扩展的标号，相当于Q标号】
    private ArrayList<ArrayList<Label>> FUL;
    // forward extended labels for each points【已扩展的标号，相当于P标号】
    private ArrayList<ArrayList<Label>> FTL;

    private Label init_label;

    // index set of column with - reduce cost
    // 存储负检验数的路径在路径池pool中的索引
    private ArrayList<Integer> gnex;

    public CG(Data data) {
        this.data = data;
        this.dp_col_size = 5;
        this.oneI = 0x00;
        this.oneII = 0x00;
        this.FUL = new ArrayList<>();
        this.FTL = new ArrayList<>();
    }

    // 列生成求解
    public boolean solve(Master master) throws IloException {
        // 在判断条件里，执行一次列生成求解
        if (!master.solve()) {
            System.out.println("!!!!!---slack false---!!!!!!");
        }

        // 获取对偶值（用于计算检验数）
        master.set_dual();

        // 持续寻找负检验数的列，并入基
        boolean isNotEnd = true;
        while (isNotEnd) {
            isNotEnd = dss(master);
        }

        return true;
    }

    /**
     * 找出负的检验数的列
     * 标号法，求解 Pricing Problem
     */
    public boolean dss(Master master) throws IloException {
        // 如果超出最大时间，则直接结束程序
        if (data.getConf().time_out()) {
            System.out.println("time_out in dss");
            System.exit(0);
        }

        // list to store the neg_col index
        ArrayList<Integer> neg_index = new ArrayList<>();
        // 从0的label出发，寻找负检验数的TSP路径
        init_label = new Label(data);
        init_label.setId(0);
        init_label.setC(-master.getDual()[0]);
        init_label.setNI(0X01);
        init_label.setFather(null);

        // 初始化FUL，FTL
        FUL = new ArrayList<>();
        FTL = new ArrayList<>();
        for (int i = 0; i < data.getN(); i++) {
            ArrayList<Label> ful = new ArrayList<>();
            FUL.add(ful);
            ArrayList<Label> ftl = new ArrayList<>();
            FTL.add(ftl);
        }
        // let initial depot and terminal in FUL and BUL
        FUL.get(0).add(init_label);
        // net_col get during the extend
        gnex = new ArrayList<>();

        //-------------------------------------------- extending------------------------------------------
        forward_extend(master);

        //-------------------------------- get the negative cost route index------------------------------
        // 重新存储一次负检验数列索引
        for (int i = 0; i < gnex.size(); i++) {
            neg_index.add(gnex.get(i));
        }

        // 如果找到了负检验数的列，就添加列，否则直接输出false
        if (neg_index.size() > 0) {
            master.add_col(neg_index);
            master.solve();
            master.set_dual();
            FUL.clear();
            FUL = null;
            FTL.clear();
            FTL = null;
            neg_index.clear();
            gnex.clear();
            return true; // we found neg_col and add it
        } else {
            FUL.clear();
            FUL = null;
            FTL.clear();
            FTL = null;
            neg_index.clear();
            gnex.clear();
            return false; // we did not find neg_col  it's over
        }
    }

    /**
     * 从未扩展结点出发，构建路径
     * 从P标号点出发，扩展Q标号为P标号，并构建路径
     */
    public void forward_extend(Master master) {
        while (true) {
            // 如果超出最大运行时长限制，不能直接结束程序，应该是把现有找到的附检验数列添加
            if (data.getConf().time_out()) {
                System.out.println("time_out in forward_extend");
                break;
            }

            //---------------------------------------- select a non extend label to extend--------------------------------
            // 从FUL中找出一个未扩展的label
            Label f_label = null;
            for (int i = 0; i < FUL.size(); i++) {
                if (FUL.get(i).size() > 0) {
                    f_label = FUL.get(i).get(0);
                    FUL.get(i).remove(0);
                    break;
                }
            }
            // 如果所有的节点都已经扩展过了，FUL已经空了
            if (f_label == null) {
                System.out.println("!!!!!!!!!!!! FUL null ===> finished all extension ===> break ");
                break;
            }
            // 将从FUL找出的label列入FTL
            FTL.get(f_label.getId()).add(f_label);

            //---------------------------------------- traverse all customer points trying to extend ---------------------
            // 从 f_label出发，寻找new_label（可以是一个或多个）
            // 从FUL中的label出发，寻找新的FUL
            long mark = 0x01;
            for (int i = 1; i < data.getN(); i++) {
                // 跳过自身节点
                mark *= 2;
                if ((f_label.getNI() & mark) != 0) continue;

                // 定义 f_label的扩展结点 new_label
                Label new_label = new Label(data);
                new_label.setId(i);
                new_label.setC(f_label.getC() + data.getC()[f_label.getId()][i] - master.getDual()[i]);
                new_label.setNI(f_label.getNI() | mark);
                new_label.setFather(f_label);

                // 占优剪支
                if (dominate(new_label)) continue;
                FUL.get(new_label.getId()).add(new_label);

                // 路径可行性
                if (!feasible_route(new_label)) continue;

                // price problem 是用来求负检验数，因此检验数为正的应该去掉
                double cost = new_label.getC() + data.getC()[new_label.getId()][0];

                if (cost > -tolerance) continue;

                // 获取这条完整路径
                ArrayList<Integer> route = get_route(new_label);

                // 将路径添加到路径池中
                if (master.getPool().route2i(route) != -1) continue;
                int index = master.getPool().add_route(route);
                System.out.println("路径 "+(master.getPool().getRoute_Pool().size()-1)+" 的检验数为："+cost);
                gnex.add(index);
            }

            // 一共找到的负检验数的路径不大于特定数量
            if (gnex.size() > dp_col_size) break;
        }
    }

    // 判断此Label是否构成一条完整路径
    // 当label全为1的时候，才算是一个合格的路径
    public boolean feasible_route(Label label) {
        long mark = 0x01;
        // 从1开始，因为 0 默认在其中
        for (int i = 1; i < data.getN(); i++) {
            mark *= 2;
            // 不能构成完整路径
            if ((label.getNI() & mark) == 0) return false;
        }
        return true;
    }

    // 返回label所在的一条完整的TSP路径
    public ArrayList<Integer> get_route(Label label) {
        ArrayList<Integer> route = new ArrayList<>();
        Label a_label;
        a_label = label;
        while (a_label.getFather() != null) {
            route.add(0, a_label.getId());
            a_label = a_label.getFather();
        }
        route.add(0, 0);
        route.add(0);
        return route;
    }

    /**
     * dominate rule【是否需要剪支】
     * 占优剪支，判断已存在l.id的label是否优于此l。在FUL和FTL中都进行搜索
     */
    public boolean dominate(Label l) {
        ArrayList<Label> q = new ArrayList<>();

        // 1.worse than all Label(id) in FTL
        q = FTL.get(l.getId());
        if (q != null) {
            for (int i = 0; i < q.size(); i++) {
                Label r = q.get(i);

                // visit same nodes NI: nodes points that have passed
                // 跳过不同id的label
                if ((l.getNI() & r.getNI()) != l.getNI()) continue;
                if ((l.getNI() & r.getNI()) != r.getNI()) continue;

                // cost less【如果c值小于已存在的label，则不需要剪支】
                if (l.getC() < r.getC()) continue;

                // 如果前面的都不满足，那就必须剪支了
                return true;
            }
        }

        // 2.worse than all Label(id) in FUL
        q = FUL.get(l.getId());
        if (q != null) {
            for (int i = 0; i < q.size(); i++) {
                Label r = q.get(i);
                // visit same nodes
                if ((l.getNI() & r.getNI()) != l.getNI()) continue;
                if ((l.getNI() & r.getNI()) != r.getNI()) continue;
                // cost less【如果c值小于已存在的label，则不需要剪支】
                if (l.getC() < r.getC()) continue;

                // 如果前面的都不满足，那就必须剪支了
                return true;
            }
        }

        /* new_label is not useless but should it can a old one? */
        /* 如果Label l 占优于已有的Label，则从FTL和FUL中删除劣势的Label */

        // 3.replace Label(id) by new_label in FTL
        q = FTL.get(l.getId());
        if (q != null) {
            for (int i = 0; i < q.size(); i++) {
                Label r = q.get(i);
                // visit same nodes
                if ((l.getNI() & r.getNI()) != r.getNI()) continue;
                if ((l.getNI() & r.getNI()) != r.getNI()) continue;
                // 成本占优检验
                if (r.getC() <= l.getC()) continue;
                // 删除原FTL中处于劣势的Label
                q.remove(r);
                i--;
            }
        }

        // 4.replace Label(id) by new_label in FTL
        q = FUL.get(l.getId());
        if (q != null) {
            for (int i = 0; i < q.size(); i++) {
                Label r = q.get(i);
                // visit same nodes
                if ((l.getNI() & r.getNI()) != r.getNI()) continue;
                if ((l.getNI() & r.getNI()) != r.getNI()) continue;
                // 成本占优检验
                if (r.getC() <= l.getC()) continue;
                // 删除原FTL中处于劣势的Label
                q.remove(r);
                i--;
            }
        }

        return false;
    }
}